package lc.q201_250;

import java.util.HashMap;
import java.util.Map;

/**
 * 同构字符串
 *
 * 给定两个字符串 s 和 t，判断它们是否是同构的。
 *
 * 如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。
 *
 * 所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/isomorphic-strings
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 输入: s = "egg", t = "add"
 * 输出: true
 *
 * 输入: s = "foo", t = "bar"
 * 输出: false
 *
 * @author lgb
 * @date 2020/08/23
 **/
public class Q205 {

    public boolean isIsomorphic(String s, String t) {
        if (s == null) {
            return t == null;
        }
        if (t == null) {
            return false;
        }
        int length = s.length();
        if (length != t.length()) {
            return false;
        }
        Map<Character, Character> c = new HashMap<>();
        Map<Character, Character> c2 = new HashMap<>();
        for (int i = 0; i < length; i++) {
            char sc = s.charAt(i);
            char tc = t.charAt(i);
            if (c.containsKey(sc) && tc != c.get(sc)) {
                return false;
            }
            if (c2.containsKey(tc) && sc != c2.get(tc)) {
                return false;
            }
            c.put(sc, tc);
            c2.put(tc, sc);
        }
        return true;
        // 思路2，两个字符串都转义到第三种字符串，也就是按照某种算法做一种映射，如果映射后的值一样就一样
    }
    public boolean isIsomorphic2(String s, String t) {
        return trans(s).equals(trans(t));
    }

    private String trans(String s) {
        // 如果某个字母第一次出现，则它对应的值是之前出现过的字母数+1
        // 否则，可以知道之前它的数是多少
        int[] alpha = new int[128];
        StringBuilder sb = new StringBuilder();
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (alpha[c] == 0) {
                count += 1;
                alpha[c] = count;
            }
            sb.append(alpha[c]);
        }
        return sb.toString();
    }

}
